P15575 [USACO26FEB] Point Elimination S Solution

前言

赛时首切，思路应该还是比较简单的。

题解

题目分析

交换 $y$ 只会改变“哪个 $y$ 配到哪个 $x$”，不会改变：

• 所有 $x$ 的多重集合
• 所有 $y$ 的多重集合

所以可以把最终删除方案看成两部分：

• 一部分配对走横向边
• 一部分配对走纵向边

设总配对数 $mid=n \div 2$。若横向有 $h$ 对、纵向有 $v$ 对，则必须满足 $h+v=mid$。

转化

• 仅看 $x$ 的多重集合，横向对数 $h$ 能取哪些值
• 仅看 $y$ 的多重集合，纵向对数 $v$ 能取哪些值
• 是否存在 $(h,v)$ 满足三者同时成立。

由此，我们可以定义一个 $calc$ 函数，输入一维坐标数组 $a$，输出：

• 最小可取值 $L$
• 最大可取值 $R$
• 固定奇偶 $P$（所有可行值同奇偶）

若无解返回 false。

具体做法

• 排序并统计每个值出现次数 $c_i$。
• 按值是否连续（相差 1）分段，段间独立。
• 对单段设 $b_k$ 为 $k$ 与 $k+1$ 间使用的相邻配对数。

每点约束：

$c_k-b_{k-1}-b_k \ge 0$ 且为偶数

• 由奇偶递推可确定每条边 $b_k$ 的奇偶基线 $p_k$，得到段最小值 $l$。
• 将 $b_k=p_k+2 \times t_k$，转成路径容量约束，贪心求 $\sum t_k$ 最大，得到段最大值 $r$。
• 全段累加到全局 $(L,R)$，奇偶累加到 $P$。

合并

设：

• $x$ 维可行：$h \in [l_x,r_x],h \equiv p_x \pmod 2$
• $y$ 维可行：$v \in [l_y,r_y],v \equiv p_y \pmod 2$

又 $v=mid-h$，故：

$$h\in[l_x,r_x]\cap[mid-r_y,\ mid-l_y]$$

并且奇偶必须匹配：

$$(p_x+p_y) \equiv mid \pmod 2.$$

若交集非空，且其中存在满足 $h\equiv px\pmod2$ 的整数，则答案 YES，否则 NO。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <functional>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
    using namespace std;
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,x[N],y[N],val[N],cnt[N],c[N],p[N],d[N];
inline bool calc (ll *a,ll &L,ll &R,ll &P) {
    sort(a+1,a+n+1);
    ll m=0;
    for (ll i=1;i<=n;i++) {
        if (!m||val[m]!=a[i]) {
            val[++m]=a[i];
            cnt[m]=1;
        }
        else {
            cnt[m]++;
        }
    }
    L=R=P=0;
    ll i=1;
    while (i<=m) {
        ll j=i;
        while (j+1<=m&&val[j+1]==val[j]+1) {
            j++;
        }
        ll sum=0;
        for (ll k=i;k<=j;k++) {
            sum+=cnt[k];
        }
        if (sum&1) {
            return false;
        }
        ll len=j-i+1;
        for (ll k=1;k<=len;k++) {
            c[k]=cnt[i+k-1];
            p[k]=0;
            d[k]=0;
        }
        p[0]=0;
        ll l=0;
        for (ll k=1;k<len;k++) {
            p[k]=(c[k]-p[k-1])&1;
            l+=p[k];
        }
        if ((c[len]-p[len-1])&1) {
            return false;
        }
        for (ll k=1;k<=len;k++) {
            ll lt=p[k-1],rt=(k==len?0:p[k]);
            ll num=c[k]-lt-rt;
            if (num<0||(num&1)) {
                return false;
            }
            d[k]=num/2;
        }
        ll lenl=0,lt=0;
        for (ll k=1;k<len;k++) {
            ll res=d[k]-lt;
            if (res<0) {
                return false;
            }
            ll cntl=min(res,d[k+1]);
            lenl+=cntl;
            lt=cntl;
        }
        if (lt>d[len]) {
            return false;
        }
        ll r=l+lenl*2;
        L+=l;
        R+=r;
        P=(P+(l&1))&1;
        i=j+1;
    }
    return true;
}
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        x[i]=read();
        y[i]=read();
    }
    ll lx,rx,px,ly,ry,py;
    bool fl=calc(x,lx,rx,px);
    bool flg=calc(y,ly,ry,py);
    if (!fl||!flg) {
        puts("NO");
        return;
    }
    ll mid=n>>1;
    if (((px+py)&1)!=(mid&1)) {
        puts("NO");
        return;
    }
    ll l=max(lx,mid-ry),r=min(rx,mid-ly);
    if (l>r) {
        puts("NO");
        return;
    }
    if ((l&1)!=px) {
        l++;
    }
    if (l<=r) {
        puts("YES");
    }
    else {
        puts("NO");
    }
}
praise_long_long main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}
/**/